---
title: "班级活动"
created: 2025-11-28
tags:
  - 算法
---

# 班级活动

## 题目 [班级活动](https://www.lanqiao.cn/paper/4103/problem/17153/)

![[image-7e051b92.png]]

## 思路分析

注意 题目是说 要成对出现 且同样的数存在两个 即否决了4 6 8这样的对

一开始没看到这一点 自以为是地用异或去写

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N=1e5+10;
unordered_map<int,bool> a;
int n;

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;

	while(n--){
		int x;cin>>x;
		a[x]^=1;
	}

	int cnt=0;
	for(auto x:a){
//		cout<<x.first<<" "<<x.second<<endl;
		if(x.second==1)
			cnt++;
	}
	cout<<cnt/2;//cnt + divisor - 1 实现除以 divisor向上取整
	return 0;
 }
```

加上这点 每个只能两次的限制 问题其实就变成了贪心的平均数那块的模板

小于2的一定被补 大于2的一定补给小于2的 等于2的肯定不动 因为补给其他人到时候又要被补回来 走了无效的重复路

令id唯一的集合为A（只出现一次的元素） 必须修改的集合为B（出现两次以上的元素）

可分为两种情况

1、B≥A时

假设有一个 id  集合 A = { 1 , 2 , 3 , 4 , 4 , 4 , 4 , 5 , 5 , 5 , 5 , 5
}

此时 id  唯一的集合为 { 1 , 2 , 3 }

必须修改的 id 集合为 { 4 , 4 , 5 , 5 , 5 }

只需要让后一个集合的 id 分别修改为 { 1 , 2 , 3 , 6 , 6 }  即可符合要求

这种情况下 需要修改的数量为 b

2、B<A时

假设有一个 id 集合 A = { 1 , 2 , 3 , 4 , 5 , 5 , 5 , 5 , 5 , 5 , 6 , 7 }

此时 id  唯一的集合为 { 1 , 2 , 3 , 4 , 6 , 7 }

必须修改的 id  集合为 { 5 , 5 , 5 , 5 }

按照同样策略 让必须修改的 id 集合与 id 唯一的集合对应上 即将必须修改的 id 集合变为 { 1 , 2 , 3 , 4 } 但此时仍然发现
id  唯一的集合剩余的两个 id  为 { 6 , 7 }

我们需要让它们一致，所以需要修改其中一个

假设剩余 4  个呢？那我们需要修改 2 个

假设剩余 8  个呢？那我们需要修改 4 个

显然结论就是需要修改剩余 id 个数的一半，

即这种情况下答案是： b+(a-b/2)

## 代码实现

```cpp
 #include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N=1e5+10;
unordered_map<int,int> all;
int n;

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;

	while(n--){
		int x;cin>>x;
		all[x]++;
	}
	int a=0,b=0;
	for(auto x:all){
//		cout<<x.first<<" "<<x.second<<endl;
		if(x.second==1)			a++;
		else if(x.second>2)		b+=x.second-2;
	}
	if(b>=a)	cout<<b<<endl;
	else	cout<<b+((a-b)/2)<<endl;
	return 0;
 }
```

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

//多模拟几组案例可以发现 首先要把每个id记下数

//如果id小于2 说明肯定要改 或者等一个改成它

//如果id大于2 那么多出2的部分一定要改成其他的

// 1 2 2 2 2 2 3 4

// 22 3个2 分别改成 1 3 4 改三个数 这是多余部分（必须要改的部分） 恰好等于可能要改的部分的情况

// cost = 出现次数大于2的数量

// 1 2 2 2 3 4

// 22 1个2 改成1 3改成4 改两个数 这是多余部分（必须要改）的数 小于可能要改的数的情况

// cost = 出现次数大于2的数量 + 没被消耗完的 出现一次的数量 再除以2

// 1 1 2 2 2 2

// 11 22 多2个2 把22都改成33 改两个数 这是多余部分 大于 可能要改的部分的情况

//综上 先用值做下标计数 统计一下 出现一次的个数 以及 超过2部分的个数

// 若cnt2>=cnt1 则答案为cnt2

// 若cnt2<cnt1 则答案为 cnt2 + (cnt1-cnt2)/2

const int N=1e5+10;

int have[N];

int n;

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n;

	int maxv=0;

	for(int i=0;i<n;i++){

		int x;cin>>x;

		have[x]++;

		maxv=max(maxv,x);

	}

	int cnt1=0,cnt2=0;

	for(int i=0;i<=maxv;i++){

		if(have[i]==1)

			cnt1++;

		if(have[i]>2){

			cnt2+=have[i]-2;

		}

	}

	if(cnt2>=cnt1)	cout<<cnt2<<endl;

	else	cout<<cnt2+((cnt1-cnt2)/2);

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[双子数|双子数]] 🏠 [[00-冲刺国赛]] ➡️ [[合并数列|合并数列]]